from itertools import combinations

def get_frequent_items(transactions, min_support):
    item_count = {}
    for transaction in transactions:
        for item in transaction:
            if item not in item_count:
                item_count[item] = 0
            item_count[item] += 1

    num_transactions = len(transactions)
    frequent_items = {item: count / num_transactions for item, count in item_count.items() if count / num_transactions >= min_support}
    return frequent_items


def generate_candidate_sets(frequent_itemsets, k):
    candidates = set()
    items = list(frequent_itemsets.keys())
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            l1 = list(items[i])[:k - 2]
            l2 = list(items[j])[:k - 2]
            if l1 == l2:
                candidate = tuple(sorted(set(items[i]).union(set(items[j]))))
                if all(tuple(subset) in frequent_itemsets for subset in combinations(candidate, k - 1)):
                    candidates.add(candidate)
    return candidates


def prune_candidates(candidates, frequent_itemsets, k):
    pruned_candidates = set()
    for candidate in candidates:
        if all(tuple(subset) in frequent_itemsets for subset in combinations(candidate, k - 1)):
            pruned_candidates.add(candidate)
    return pruned_candidates


def apriori(transactions, min_support):
    frequent_itemsets = {}
    k = 1
    while True:
        if k == 1:
            frequent_k_itemsets = get_frequent_items(transactions, min_support)
        else:
            candidate_sets = generate_candidate_sets(frequent_itemsets, k)
            candidate_counts = {candidate: 0 for candidate in candidate_sets}

            for transaction in transactions:
                for candidate in candidate_sets:
                    if set(candidate).issubset(transaction):
                        candidate_counts[candidate] += 1

            num_transactions = len(transactions)
            frequent_k_itemsets = {item: count / num_transactions for item, count in candidate_counts.items() if count / num_transactions >= min_support}

        if not frequent_k_itemsets:
            break

        frequent_itemsets.update(frequent_k_itemsets)
        k += 1

    return frequent_itemsets


# 示例数据
transactions = [
    {'milk', 'bread'},
    {'bread', 'butter'},
    {'milk', 'bread', 'butter'},
    {'bread', 'jam'},
    {'milk', 'jam'}
]

min_support = 0.4
frequent_itemsets = apriori(transactions, min_support)

print("Frequent Itemsets:")
for itemset, support in frequent_itemsets.items():
    print(f"{itemset}: {support}")



